class Solution {
public:
    TreeNode* res = nullptr;
    TreeNode* prev = nullptr;
    TreeNode* Convert(TreeNode* root) {
        if (root == nullptr) return nullptr;
        Convert(root->left);
        if (prev == nullptr) {
            res = root;
            prev = root;
        } else {
            prev->right = root;
            root->left = prev;
            prev = root;
        }
        Convert(root->right);
        return res;
    }
};
